#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
 struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 };
 
#include <climits>
class Solution {
public:
    int recursion(TreeNode* cur, int* Max)
    {
        if (!cur)
        {
            return 0;
        }
        int x = recursion(cur->left, Max);
        int y = recursion(cur->right, Max);
        if (cur->val + x > *Max) *Max = cur->val + x;
        //cout<<cur->val+x<<endl;
        if (cur->val + y > *Max) *Max = cur->val + y;
        if (cur->val + x + y > *Max) *Max = cur->val + x + y;
        if (cur->val > *Max) *Max = cur->val;
        //cout<<*Max<<endl;
        return max(x + cur->val, y + cur->val);
    }
    void A(TreeNode* cur, int n)
    {
        if (!cur)
        {
            cerr << "[" << n << "]" << "N ";
            return;
        }
        cerr << "[" << n << "]" << cur->val << " ";
        A(cur->left, n + 1);
        A(cur->right, n + 1);
        return;
    }
    int maxPathSum(TreeNode* root)
    {
        //A(root,1);
        int max = INT_MIN;
        recursion(root, &max);
        cerr << "max=" << max << endl;
        return max;
    }
};